Maryam invests in companies on the stock market. She is currently considering 50 potential companies she can invest in and has estimated the potential profit she is likely to receive from each company over the next 12 months. The investment in each company has an initial cost and Maryam has a fixed budget that she cannot exceed. Describe a dynamic programming algorithm that Maryam can use to select a set of companies to invest in that will provide maximum profit for her budget.
The following is an example of a high-scoring response.
Solve using the approach for the 1|0 knapsack problem. Through a bottom up approach with memorization, she could progressively find the most profitable combinations from T(0) to T(budget), at each stage setting T(n) as max{𝑐𝑛,𝑇(𝑛−𝑖)+𝑇(𝑖)} and incrementing 𝑖 by 1 at each iteration. Once T(budget) is obtained, she can backtrack to find the combination of most profitable companies to invest in for her budget, as each company can only be invested once.
Seems to have mixed up top down and bottom up approaches.
bottom-up is tabulation
memoisation is the top-down recursive
What is \(T(n)\) and what is \(c_n\)?
Maybe they meant to write:
Maryam can use a top-down dynamic programming solution with memoisation. A recursive function is called with the remaining budget and the next company, returning the maximum profit by either skipping the company or including it if affordable. Subproblem results are stored so each budget–company combination is solved once, ensuring an overall time of O(n × budget).
Maryam can use a bottom-up dynamic programming approach. She builds a table where each entry represents the best profit achievable for a given budget using the first i companies. At each stage, she updates the table by either skipping the company or including it if the cost fits, and the final entry for the full budget gives the maximum profit in O(n × budget) time.